package com.qxy.practice.collection.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
              this.left = left;
              this.right = right;
          }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return bfs(root);

    }
    private boolean bfs(TreeNode root){
        if(root == null) {
            return true;
        }
        TreeNode cur  = root;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while(!que.isEmpty()){
            List<Integer> curLoop = new ArrayList<>();
            int pollNum = que.size();
            while(pollNum>0){
                TreeNode tmp =  que.poll();
                curLoop.add(tmp.val);
                if(tmp.left != null) {
                    que.offer(tmp.left);
                }
                if(tmp.right != null) {
                    que.offer(tmp.right);
                }
                pollNum--;
            }
            if(!checkIter(curLoop)){
                return false;
            }
        }
        return true;
    }
    private boolean checkIter(List<Integer> list){
        int left = 0;
        int right = list.size();
        while(left<right){
            if(!list.get(left).equals(list.get(right))){
                return false;
            }
        }
        return true;
    }
}